package com.zklh.leetcode.top100;

/**
 * 前缀树算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/11/1
 */
public class Solution208 {
    static class Trie {
        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            children = new Trie[26];
        }

        public void insert(String word) {
            Trie node = this;
            char[] chars = word.toCharArray();
            for (char aChar : chars) {
                if (node.children[aChar - 'a'] == null) {
                    node.children[aChar - 'a'] = new Trie();
                }
                node = node.children[aChar - 'a'];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            char[] chars = word.toCharArray();
            Trie node = this;
            for (char aChar : chars) {
                if (node.children[aChar - 'a'] != null) {
                    node = node.children[aChar - 'a'];
                } else {
                    return false;
                }
            }
            return node.isEnd;
        }

        public boolean startsWith(String prefix) {
            return searchPrefix(prefix) != null;
        }

        private Trie searchPrefix(String prefix) {
            char[] chars = prefix.toCharArray();
            Trie node = this;
            for (char aChar : chars) {
                if (node.children[aChar - 'a'] != null) {
                    node = node.children[aChar - 'a'];
                } else {
                    return null;
                }
            }
            return node;
        }
    }
}